ll fpow(ll base,ll pow,ll mod){ //长整型快速幂算法
	ll ans=1;
	while(pow){
		if(pow&1){
			ans*=base;
			ans%=mod;
		}
		base*=base;
		base%=mod;
		pow>>=1;
	}
	
	return ans;
}

__int128 fpow(__int128 base,__int128 pow,__int128 mod) { //高精度快速幂算法
	__int128 ans=1;
	while (pow) {
		if (pow&1) {
			ans=ans*base%mod;
		}
		base=base*base%mod;
		pow>>=1;
	}

	return ans;
}